package digui;

import java.util.Map;

public class _05二分查找变体 {
    //有序的查找使用二分法
     public static void main(String[] args) {
        /*int[] arr = {5,1,2,3,4};
        int res = min(arr);
        System.out.println(res);*/
        /*String[] a ={"a", "", "ac","","ad","b","","ba"};
        int ans = indexof(a,"a");
         System.out.println(ans);*/
        int[] a = {5,1,2,3,1};
        //int ans = findLongest(a);
        int ans = findLongestCon(a);
         System.out.println(ans);
    }


    //二分查找递归
    static int binarySearch1(int[] arr,int low,int high,int key){
        if (low > high) return -1;
        int mid = low +((high - low) >> 1);
        int midVal = arr[mid];
        if (midVal < key){
            binarySearch1(arr,mid+1,high,key);
        }else if (midVal > key){
            binarySearch1(arr,low,mid-1,key);
        }else
            return mid;
        return 0;
    }



    /**
     * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，
     * 输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
     * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
     */
    private static int min(int[] arr) {
        int begin = 0 ;
        int end = arr.length - 1;
        if (arr[begin] < arr[end]) return arr[begin];
        while (begin + 1 < end){
            int mid = begin +((end - begin) >> 1);
            //要么左侧有序，要么右侧有序
            if (arr[mid] >= arr[begin]){
                //左侧有序
                begin = mid;
            }else {
                //右侧有序
                end = mid;
            }
        }
        return arr[end];
    }

    //有个排序后的字符串数组,其中散布着一些空字符串 ,编写一个方法,找出给定字符串(肯定不是空字符串)的索引
    private static int indexof(String[] a, String p) {
        int begin = 0;
        int end = a.length-1;
        while (begin <= end) {
            int indexOfMid = begin + ((end - begin) >> 1);
            while (a[indexOfMid].equals("")){
                indexOfMid++;
                if (indexOfMid ++ > end){
                    return -1;
                }
        }
            if (a[indexOfMid].compareTo(p)>0){
                //中值比目标大，目标落在左半区间
                end = indexOfMid-1;
            }else if (a[indexOfMid].compareTo(p)<0){
                //中值比目标小，目标落在右半区间
                begin = indexOfMid+1;
            }else {
                return indexOfMid;
            }
        }
        return -1;
    }


    //最长递增子序列（部分有序）

    /**
     * 示例 1：
     *
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     * 示例 2：
     *
     * 输入：nums = [0,1,0,3,2,3]
     * 输出：4
     * 示例 3：
     *
     * 输入：nums = [7,7,7,7,7,7,7]
     * 输出：1
     * @param array
     * @return
     */
    public static int findLongest(int[] array){
        int[] max = new int[array.length];
        for (int i = 0; i <array.length ; i++) {
            max[i] = 1;
        }
        for (int i = 1; i < array.length ; i++) {
            for (int j = 0; j < i ; j++) {
                if (array[i] > array[j] && max[i] < max[j] + 1) {
                    max[i] = max[j] + 1;
                }
            }
        }
        int maxLen = 0;
        for (int i = 0; i < array.length ; i++) {
            if (maxLen < max[i]) {
                maxLen = max[i];
            }
        }
        return maxLen;
    }

    //最长连续递增子序列（部分有序）
    //2,1,4,3,1,5,6   1,5,6 ---> 3
    //10,9,2,5,3,7,101,18  -->3,7,101  3
    public static int findLongestCon(int[] a){
        int num = 0 ;
        int max =0 ;
        for (int i = 0 ; i < a.length -1 ; i++) {
            if (a[i+1] > a[i]){
                num ++;
                if (num > max){
                    max = num;
                }
            }else {
                num = 0;
            }
        }
        return max+1;
    }


}
